package gold.digger;

import gold.utils.InputUtil;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC213 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        public int rob(int[] arr) {
            if (null == arr || arr.length <= 0) return 0;

            int n = arr.length - 1;
            int lastChoose = arr[n] + robInSingleLine(arr, 1, n - 2);
            int lastNotChoose = robInSingleLine(arr, 0, n - 1);
            return Math.max(lastChoose, lastNotChoose);
        }

        public int robInSingleLine(int[] arr, int start, int end) {
            if (start > end) return 0;
            if (start == end) return arr[start];
            if (end - start == 1) return Math.max(arr[start], arr[end]);

            int dp[] = new int[end - start + 1];
            dp[0] = arr[start];
            dp[1] = Math.max(arr[start + 1], arr[start]);
            for (int i = start + 2; i <= end; i++) {
                dp[i - start] = Math.max(arr[i] + dp[i - start - 2], dp[i - start - 1]);
            }

            return dp[end - start];
        }
    }

    public void run() {
        Solution solution = new Solution();
        int[] arr = InputUtil.toIntegerArray("[4,1,2,7,5,3,1");
        System.out.println(solution.rob(arr));
    }

    public static void main(String[] args) throws Exception {
        LC213 an = new LC213();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
